/**
 * 字母异位词分组
 *
 * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 *
 * 示例 1:
 * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 * 解释：
 * 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
 * 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
 * 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。
 *
 * 示例 2:
 * 输入: strs = [""]
 * 输出: [[""]]
 *
 * 示例 3:
 * 输入: strs = ["a"]
 * 输出: [["a"]]
 *
 * 提示：
 * 1 <= strs.length <= 104
 * 0 <= strs[i].length <= 100
 * strs[i] 仅包含小写字母
 */

import java.util.*;
import java.util.stream.Collectors;

/**
 * 要咱求相同的 字母集合, 如何判断他们相同呢, 我们可以让 String 变为 字符数组
 * 然后在按照字典序排序, 再转换为 String, 后面要是遇到相同的字符串, 那就是相同
 * 字母组成的, 对此我们还需要创建一个容器来装 集合, 并且还要标识这个 集合是存储啥
 * 类型的字母的, 那就是 map 了
 * 时间复杂度 : O(n * k * logK)
 * 空间复杂度 : O(n * k)
 */

public class Main {
    public List<List<String>> groupAnagrams(String[] strs) {

        // 创建一个容器
        Map<String, List<String>> hash = new HashMap<>();

        // 遍历字符串数组
        for (String s : strs) {

            // 转为字符数组
            char[] ch = s.toCharArray();

            // 排序
            Arrays.sort(ch);

            // 再转为字符串
            String ss = new String(ch);

            // 这里要是第一次小出现, 要创建 list
            if (!hash.containsKey(ss)) {
                hash.put(ss, new ArrayList<>());
            }

            // 有 集合后再将 原字符串加入 集合
            hash.get(ss).add(s);
        }

        // 这里我们直接将 map的 values, 转为 lists
        return new ArrayList<>(hash.values());
    }

    // 观摩观摩, 学习学习
    public List<List<String>> groupAnagrams3(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs)
                .collect(Collectors.groupingBy(str -> {
                    // 返回 str 排序后的结果。
                    // 按排序后的结果来grouping by，算子类似于 sql 里的 group by。
                    char[] array = str.toCharArray();
                    Arrays.sort(array);
                    return new String(array);
                })).values());
    }


    public List<List<String>> groupAnagrams2(String[] strs) {
        Map<Integer, List<String>> map = new HashMap();
        List<List<String>> res = new ArrayList();
        for(String str : strs){
            int key = getKey(str);
            if(map.containsKey(key)){
                List<String> list = map.get(key);
                list.add(str);
            }
            else{
                List<String> list = new ArrayList<String>();
                list.add(str);
                map.put(key, list);
                res.add(list);
            }
        }
        return res;
    }

    public int getKey(String str){
        int sum = 0;
        for(int i = 0; i < str.length(); i++){
            char ch = str.charAt(i);

            // 这个也是高手
            sum += (ch*(ch - 1)*ch*ch - ch);
        }
        return sum;
    }

    public static void main(String[] args) {
        Main test = new Main();
        System.out.println(test.getKey("duh"));
        System.out.println(test.getKey("paw"));
    }
}